package lru.review5_21;

import java.util.HashMap;
import java.util.Map;

//  CKG TODO 2023/5/21: 主要就是范型的使用不熟练
public class LRUByHand {
    //  CKG TODO 2023/5/21:  同时有多个类的时候我竟然不知道如何进行定义构造器
    //  CKG TODO 2023/5/21: 缺少范型  定义错误  学会使用范型
    class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;

        public Node() {
            this.prev = this.next = null;
        }

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.prev = this.next = null;
        }
    }


    class DoubleLinkedList<K, V> {
        Node<K, V> head;
        Node<K, V> tail;

        //  CKG TODO 2023/5/21: 构建一个空的双向链表
        public DoubleLinkedList() {
            head = new Node<>();
            tail = new Node<>();
            head.next = tail;
            tail.prev = head;
        }

        //  CKG TODO 2023/5/21: 保证最近常使用的靠近头部
        public void addHead(Node<K, V> node) {
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
        }

        //  CKG TODO 2023/5/21:  尾部都是最不长使用的
        public void removeNode(Node<K, V> node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.prev = null;
            node.next = null;
        }

        public Node getLast() {
            return tail.prev;
        }
    }




    private int cacheSize;
    Map<Integer, Node<Integer, Integer>> map;
    DoubleLinkedList<Integer, Integer> doubleLinkedList;


    public LRUByHand(int cacheSize) {
        this.cacheSize = cacheSize;
        map = new HashMap<>();
        doubleLinkedList = new DoubleLinkedList<>();
    }


    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node<Integer, Integer> node = map.get(key);
        //  CKG TODO 2023/5/21: 进行了查找就要将该数值在链表中的位置提前
        doubleLinkedList.removeNode(node);
        doubleLinkedList.addHead(node);
        return node.value;
    }


    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node<Integer, Integer> node = map.get(key);
            node.value = value;
            //  CKG TODO 2023/5/21:  修改完数值后要重新放入到map 中
            map.put(key, node);
            doubleLinkedList.removeNode(node);
            doubleLinkedList.addHead(node);
        } else {
            if (map.size() == cacheSize) {
                Node last = doubleLinkedList.getLast();
                map.remove(last.key);
                doubleLinkedList.removeNode(last);
            }
            Node<Integer, Integer> newNode = new Node<>(key, value);
            map.put(key, newNode);
            doubleLinkedList.addHead(newNode);
        }
    }

    public static void main(String[] args) {
        LRUByHand lruByHand = new LRUByHand(3);
        lruByHand.put(1,1);
        lruByHand.put(2,1);
        lruByHand.put(3,1);
        System.out.println(lruByHand.map.keySet());
        lruByHand.put(4,1);
        System.out.println(lruByHand.map.keySet());
        lruByHand.put(3,1);
        System.out.println(lruByHand.map.keySet());
        lruByHand.put(2,2);
        System.out.println(lruByHand.map.keySet());
        lruByHand.put(5,2);
        System.out.println(lruByHand.map.keySet());










    }

}


